División de Cadenas
Cierto lenguaje de procesamiento de cadenas
le permite a los programadores dividir una cadena en dos partes. Debido a
que esto implica copiar la cadena original, el costo de dividir en dos una
cadena de k caracteres es de k unidades de tiempo.
Suponga que un programadis desea dividir unacadena S en N partes de longitud
A1, A2
, ...,AN
respectivamente. El orden en que se hagan las divisionespuede afectar la cantidad
total de tiempo que se necesita para dividir la cadena.
Escribe un programa que determine la cantidad mínima
de tiempo T que se requiere para dividir la cadena. Por ejemplo, la cadena
OLIMPIADAINFORMATICA y se quiere dividir en las cinco cadenas OLIMP, PIA,
DAIN, FORMA y TICA entonces se requiere un mínimo de 47 unidades de
tiempo, haciendo las divisiones como sigue: primero se hace la división
OLIMPIADAIN - FORMATICA ( costo 20 ), depues la división OLIM - PIADAIN
(costo 11), posteriormente la division la división PIA - DAIN ( costo
7 ) y finalmente FORMA - TIA (costo 9).
Entrada
El archivo "Input.txt" contiene en el prmer renglón
la cantidad N de partes (0 < N < 101) y en el segundo renglón
la lista de longitudes de las partes A1, A
2, ...,AN
con ( 0 < Ai < 1001)
Salida
El archivo "Output.txt" debe´ra contener en el primer
renglón al entero T.
Input.txt
|
Output.txt
|
5
4 3 5 4 4
|
47
|